package com.atguigu.greedy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @className: GreedyAlgorithm
 * @description: 贪心算法
 * @date: 2021/3/30
 * @author: cakin
 */
public class GreedyAlgorithm {
    /**
     * 功能描述：贪心算法测试
     *
     * @param args 命令行
     * @author cakin
     * @date 2021/3/30
     * @description:
     */
    public static void main(String[] args) {
        // 广播电台
        HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
        // 各个电台覆盖区域
        // K1
        HashSet<String> hashSet1 = new HashSet<>();
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");
        // K2
        HashSet<String> hashSet2 = new HashSet<>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");
        // K3
        HashSet<String> hashSet3 = new HashSet<>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");
        // K4
        HashSet<String> hashSet4 = new HashSet<>();
        hashSet4.add("上海");
        hashSet4.add("天津");
        // K5
        HashSet<String> hashSet5 = new HashSet<>();
        hashSet5.add("杭州");
        hashSet5.add("大连");
        // 构建电台和区域的关系
        broadcasts.put("K1", hashSet1);
        broadcasts.put("K2", hashSet2);
        broadcasts.put("K3", hashSet3);
        broadcasts.put("K4", hashSet4);
        broadcasts.put("K5", hashSet5);
        // 存放所有的地区
        HashSet<String> allAreas = new HashSet<>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("广州");
        allAreas.add("深圳");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大连");
        // 存放选择的电台集合
        ArrayList<String> selects = new ArrayList<>();
        // 存放电台覆盖的地区和当前还没有覆盖的地区的交集
        HashSet<String> tempSet = new HashSet<>();

        // 能够覆盖最大未覆盖的地区对应的电台的key
        // 如果 maxKey 不为 null , 则会加入到 selects
        String maxKey;
        while (allAreas.size() != 0) { // 如果allAreas 不为0, 则表示还没有覆盖到所有的地区
            maxKey = null;
            // 遍历每一个电台
            for (String key : broadcasts.keySet()) {
                tempSet.clear();
                // 当前这个电台能够覆盖的地区
                HashSet<String> areas = broadcasts.get(key);
                tempSet.addAll(areas);
                // 求出电台覆盖地区和所有要覆盖地区的交集, 交集会放到 tempSet
                tempSet.retainAll(allAreas);
                // 如果当前这个电台包含的覆盖地区的数量，比maxKey电台指向的集合地区还多，就需要重置maxKey
                // tempSet.size() > broadcasts.get(maxKey).size()) 体现出贪心算法的特点,每次都选择最优的
                if (tempSet.size() > 0 &&
                        (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) {
                    maxKey = key;
                }
            }
            // 经过一轮选择，将最优电台加入selects
            if (maxKey != null) {
                selects.add(maxKey);
                // 从 allAreas 去掉最优电台覆盖的地区
                allAreas.removeAll(broadcasts.get(maxKey));
            }
        }
        System.out.println("得到的选择结果是" + selects); // [K1,K2,K3,K5]
    }
}
